/*
    使用双指针，用指针p0来交换0，p1来交换1,初始值都为0。
    当我们从左向右遍历整个数组时：
    如果找到了1,那么将其与nums[p1]进行交换，并将P1向后移动一个位置。
    如果找到了0，那么将其与nums[p0]进行交换，并将p0向后移动一个位置。
    这样做是正确的吗?
    我们可以注意到，因为连续的0之后是连续的1,因此如果我们将0与nums[p0]进行交换，那么我们可能会把一个1交换出去。
    当p0<p1 时，我们已经将一些1连续地放在头部，此时一定会把一个1交换出去，导致答案错误。
    因此，如果p0<p1，那么我们需要再将nums[i]与nums[p1]进行交换，其中i是当前遍历到的位置。
    在进行了第一次交换后，nums[i]的值为1,我们需要将这个1放到「头部」的未端。
    在最后，无论是否有p0<p1,我们需要将p0和p1均向后移动一个位置，而不是仅将p0向后移动一个位置。
*/

void swap(int* a, int* b){
    int t = *a;
    *a = *b, *b = t;
}

void sortColors(int* nums, int numsSize){
    int p0 = 0, p1 = 0;

    for (int i = 0; i < numsSize; ++i){
        if (nums[i] == 1){
            swap(&nums[i], &nums[p1]);
            ++p1;
        }
        if (nums[i] == 0){
            swap(&nums[i], &nums[p0]);
            if (p0 < p1){
                swap(&nums[i], &nums[p1]);
            }
            ++p0;
            ++p1;
        }
    }
}